package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * 注意:
 * <p>
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1:
 * <p>
 * 输入: [1, 5, 11, 5]
 * <p>
 * 输出: true
 * <p>
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *
 * @author caijinnan
 * @date 2020/6/9 15:53
 */
public class 分割等和子集 {


    @Test
    public void run() {
        int[] nums = {1, 5, 13, 5};
        System.out.println(canPartition(nums));
    }


    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int numTemp : nums) {
            sum += numTemp;
        }
        if (sum >> 1 << 1 != sum) {
            return false;
        }
        int length = sum / 2;
        boolean[] dp = new boolean[length + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = length; i >= num; i--) {
                if (dp[length]) {
                    return true;
                }
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[length];
    }
}